Graph

References

DFS

def dfs_iterative(adj_list, start, end):
  stack = list()
  visited = set()
  stack.append(start)
  visited.add(start)
  
  while (len(stack) > 0):
      cur_node = stack.pop()
      for adj_node in adj_list[cur_node]:
          if adj_node == end:
              return True
          if adj_node in visited:
              continue
          stack.append(adj_node)
          visited.add(adj_node)
  return False

def dfs_recursion(adj_list, start, end, visited):
  if start in visited:
      return False
  if start == end:
      return True
  visited.add(start)
  for adj_node in adj_list[start]:
      if dfs(adj_list, adj_node, end, visited):
          return True
  return False

Basic implementation of DFS with stack, only work with adjacency list
- NOTES: If we find the chance to use DFS but the original data structure is not adjacency list, we can iterate over it and construct our own adjacency list to use this DFS implementation (Important pattern)
- Another pattern is counting, here we may need to traverse through the graph to check all possible path and stuff like that ⇒ Initialize an array to track all paths outside the DFS helper, and pass in as the parameter for every call and update the array in each DFS call
  - This also applies to problems where there maybe a cycle inside the graph, we can initialize an array(usually use set rather than array as it has O(1) lookup and also preserve unique characteristic) visited to keep track of visited node, and pass in as parameter for the dfs helper and update the array with new node with each call
  - Another key point is that we can setup for the dfs helper to return something to signal the change in the count, for example, the dfs will traverse all the node and return true, which means that the count can be increase

Helpful Pattern

Traverse all root to leaves path
Sometimes we have to traverse all possible path and keep record of those paths https://leetcode.com/problems/binary-tree-paths/
We can extend this for more complex requirement
- E.g: since we keep track of all the path, we can easily calculate path sum or node depths, etc

def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
    res = []
    
    def dfs(node, cur_path):
        nonlocal res
        if not node:
            return
        cur_path.append(node.val)
        if not node.left and not node.right:
            res.append('->'.join([str(i) for i in cur_path]))
            return
        if node.left:
            dfs(node.left, cur_path.copy())
        if node.right:
            dfs(node.right, cur_path.copy())
    
    dfs(root, [])
    return res

BFS

Typically used for matrix problems or shortest path problems
Template => Should memorize and be able to implement blindfolded

rows, cols = len(grid), len(grid[0])
visit = set()
queue = [(0, 0)]
directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]

while queue:
    cur_row, cur_col = queue.pop(0)
    for row_dir, col_dir in directions:
        next_row, next_col = cur_row + row_dir, cur_col + col_dir
        if (
            next_row in range(rows) and
            next_col in range(cols) and
            (next_row, next_col) not in visit and
            grid[next_row][next_col] == 0 # Or some arbitrary condition
        ):
            queue.append((next_row, next_col))
            visit.add((next_row, next_col))

This is the basic template, we can modify this a bit depends on the problem
- Sometimes this can be a helper function nested instead some other functions, each call will traverse the graph and mark some cells based on some conditions
- Sometimes we need to include something more than just (row,col) in the queue to keep track of something else
Example: [[Blind 75-150#^44f995 | Number of Island]]

https://leetcode.com/problems/shortest-path-in-binary-matrix

# Use BFS because we need to find a shortest path
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visit = set()
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

    if grid[0][0] != 0:
        return -1

    queue = [(0, 0, 1)]
    while queue:
        cur_row, cur_col, dist = queue.pop(0)
        if cur_row == rows - 1 and cur_col == cols - 1:
            return dist
        for row_dir, col_dir in directions:
            next_row, next_col = cur_row + row_dir, cur_col + col_dir
            if (
                next_row in range(rows) and
                next_col in range(cols) and
                (next_row, next_col) not in visit and
                grid[next_row][next_col] == 0
            ):
                queue.append((next_row, next_col, dist + 1))
                visit.add((next_row, next_col))
    return -1

https://leetcode.com/problems/time-needed-to-inform-all-employees

 def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
    graph = collections.defaultdict(list)
    for id, manager in enumerate(manager):
        if manager != -1:
            graph[manager].append(id)

    maxTime = 0
    queue = [(headID, 0)]

    while queue:
        curLen = len(queue)
        for _ in range(curLen):
            id, time = queue.pop(0)
            maxTime = max(time, maxTime)
            for sub in graph[id]:
                queue.append((sub, time + informTime[id]))
    
    return maxTime

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree

Important question

def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return 
    colsMap = collections.defaultdict(list)
    queue = [(root, 0, 0)]

    while queue:
        curLen = len(queue)
        for _ in range(curLen):
            node, row, col = queue.pop(0)
            colsMap[col].append((node.val, row))
            if node.left:
                queue.append((node.left, row+1, col-1))
            if node.right:
                queue.append((node.right, row+1, col+1))
    
    res = []
    for col, nodesRows in sorted(colsMap.items()):
        nodesRows.sort(key=lambda x: (x[1], x[0]))
        res.append([val for val, _ in nodesRows])
    
    return res

Helpful pattern

Absolute must read: https://leetcode.com/discuss/study-guide/1833581/bfs-and-its-variations

BFS From border

Another helpful thinking pattern is reverse, sometime it's easier to solve the problem like find path to target by traversing from target to every other nodes rather than traversing from every individual node to target

- [[Blind 75-150#^9216d6 | Rotting oranges]]

In this class of problems, you have some information available on border of grid i.e. row =0, m-1 and column =0, n-1, so BFS should start from these, lets see with some examples.

https://leetcode.com/problems/pacific-atlantic-water-flow

Traverse from each border inward and mark island as visited instead going through the matrix sequentially

 def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    rows, cols = len(heights), len(heights[0])
    directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    def bfs(row, col, visit):
        visit.add((row, col))
        queue = [(row, col)]

        while queue:
            curRow, curCol = queue.pop(0)
            for rowDir, colDir in directions:
                nextRow, nextCol = curRow + rowDir, curCol + colDir
                if (
                    nextRow in range(rows) and
                    nextCol in range(cols) and
                    (nextRow, nextCol) not in visit and
                    heights[nextRow][nextCol] >= heights[curRow][curCol]
                ):
                    visit.add((nextRow, nextCol))
                    queue.append((nextRow, nextCol))
    
    pacifc, atlantic = set(), set()
    for i in range(rows):
        bfs(i, 0, pacifc)
        bfs(i, cols-1, atlantic)

    for i in range(cols):
        bfs(0, i, pacifc)
        bfs(rows-1, i, atlantic)
    
    res = []
    for row in range(rows):
        for col in range(cols):
            if (row, col) in pacifc and (row, col) in atlantic:
                res.append((row, col))
    
    return res

Surrounded Regions - https://leetcode.com/problems/surrounded-regions/

# Traverse and mark all cell that should not be flip (adjacent to border) as visited, and traverse again to flip all cell that can be flip
def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        visit = {}
        rows, cols = len(board), len(board[0])
        
        def bfs(row, col, flip = False):
            if ((row, col) not in visit and board[row][col] == "O"):
                visit[(row, col)] = True
                directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
                if flip == True:
                    board[row][col] = "X"
                for row_dir, col_dir in directions:
                    next_row, next_col = row + row_dir, col + col_dir
                    if (next_row in range(rows) and
                        next_col in range(cols) and
                        (next_row, next_col) not in visit and
                        board[next_row][next_col] == "O"
                       ):
                        bfs(next_row, next_col, flip)
        
        for row in range(rows):
            bfs(row, 0)
            bfs(row, cols-1)
        
        for col in range(cols):
            bfs(0, col)
            bfs(rows-1, col)
            
        for row in range(rows):
            for col in range(cols):
                if (row, col) not in visit and board[row][col] == "O":
                    bfs(row, col, True)

0-1 BFS

The Core Idea:

Think of 0-1 BFS as "priority BFS" where some moves are free (cost 0) and should be processed immediately, while other moves have a cost (cost 1) and can wait their turn.

The first time we meet our target will actually be the shortest distance

- Refer to [[9. Graph#Dijkstra's Shortest Path]] to understand more on this (which is a more advanced version but the core idea is similar)

When to Use:

You'll recognize opportunities to use 0-1 BFS when you see:

- A shortest path/distance problem where moves have two distinct costs (0 and 1)
- Grid problems where moving between same-type cells is free, but changing types costs 1
- Problems asking for minimum transformations/operations where some changes are free

The Template:

def zero_one_bfs(grid):
    # Initialize
    distances = [[float('inf')] * cols for _ in range(rows)]
    queue = collections.deque()
    
    # Add starting point(s)
    queue.append(start)
    distances[start.row][start.col] = 0
    
    while queue:
        cur = queue.popleft()
        
        for next_state in get_next_states(cur):
            if is_zero_cost_move(cur, next_state):
                distances[next_state] = distances[cur]
                queue.appendleft(next_state)  # Priority processing
            else:  # cost 1 move
                distances[next_state] = distances[cur] + 1
                queue.append(next_state)  # Process later

Key Implementation Details:

Use a deque (not a regular queue)
Zero-cost moves go to front (appendleft)
Cost-1 moves go to back (append)
Track distances to avoid revisiting states

https://leetcode.com/problems/shortest-bridge

We want to finish traverse island 1 first
After this, the first time we meet island 2 is actually the shortest distance (because we traverse in priority)

 def shortestBridge(self, grid: List[List[int]]) -> int:
    rows = cols = len(grid)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = collections.deque()
    distances = [[float('inf')] * cols for _ in range(rows)]

    for row in range(rows):
        found = False
        for col in range(cols):
            if grid[row][col] == 1:
                queue.append((row, col))
                distances[row][col] = 0            
                found = True
                break
        if found:
            break

    finishedFirstIsland = False
    while queue:
        row, col = queue.popleft()

        if grid[row][col] == 0:
            finishedFirstIsland = True

        if grid[row][col] == 1 and finishedFirstIsland:
            return distances[row][col]

        for rowDir, colDir in directions:
            nextRow, nextCol = row + rowDir, col + colDir

            if (
                nextRow in range(rows) and
                nextCol in range(cols) and 
                distances[nextRow][nextCol] == float('inf') # unvisited
            ):
                distances[nextRow][nextCol] = distances[row][col]

                if grid[nextRow][nextCol] == 0:
                    queue.append((nextRow, nextCol))
                    distances[nextRow][nextCol] += 1
                else:
                    queue.appendleft((nextRow, nextCol))
    
    return -1

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/

Multisource BFS

Generally we start BFS with a single source node and then traverse, in this class of problems we are given multiple source
Example: given multiple cities and some has police stations, for each city find the nearest
- We would start BFS from the police station, and the moment we find a city from a police station, we

https://leetcode.com/problems/rotting-oranges/

def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = []
        fresh = 0
        result = 0
        
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh +=1
        
        if not fresh:
            return result
        
        while queue:
            if not fresh:
                break
            len_q = len(queue)
            result +=1
            for i in range(len_q):
                cur_row, cur_col = queue.pop(0)
                for row_dir, col_dir in directions:
                    adj_row, adj_col = cur_row + row_dir, cur_col + col_dir
                    if (
                        adj_row in range(rows) and
                        adj_col in range(cols)
                    ):
                        if grid[adj_row][adj_col] == 1:
                            grid[adj_row][adj_col] = 2
                            fresh -=1
                            queue.append((adj_row, adj_col))
        
        return result if fresh == 0 else -1

https://leetcode.com/problems/walls-and-gates/description/

Here we traverse from the gate and update all the adjacent empty room instead of traversing from empty room and stop at gate

def wallsAndGates(self, rooms: List[List[int]]) -> None:
        rows, cols = len(rooms), len(rooms[0])
        queue = []
        visit = set()
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for row in range(rows):
            for col in range(cols):
                if rooms[row][col] == 0:
                    visit.add((row, col))
                    queue.append((row, col))

        dist = 0
        while queue:
            for i in range(len(queue)):
                cur_row, cur_col = queue.pop(0)
                rooms[cur_row][cur_col] = dist

                for row_dir, col_dir in directions:
                    next_row, next_col = cur_row + row_dir, cur_col + col_dir
                    if (
                        next_row not in range(rows) or
                        next_col not in range(cols) or
                        rooms[next_row][next_col] == -1 or
                        (next_row, next_col) in visit
                    ): 
                        continue
                    visit.add((next_row, next_col))
                    queue.append((next_row, next_col))
            dist += 1

https://leetcode.com/problems/as-far-from-land-as-possible

https://leetcode.com/problems/map-of-highest-peak

BFS with bit masking

Bi-directional BFS

Variants/Algorithms

Topological Sort

https://leetcode.com/discuss/general-discussion/1078072/introduction-to-topological-sort
Another pattern in Graph section is Topological Sort
- Problems that can be modelled as a graph with directed edges where some events must occur before others
  - School class prerequisites
  - Program dependencies
  - Event scheduling
  - Etc
Topological Sort algorithm can find a topological ordering in O(V+E)
- Topological ordering is an ordering of the nodes in a directed graph where for each directed edge from node A to node B, node A appears before node B in the ordering
- Not every graph can have a topological ordering ⇒ Graph that contains a cycle
- The only type of graph that can contain topological ordering is Directed Acyclic Graphs (DAG) (Tree is also a DAG by definition)
Idea: DFS-Based Approach:
- Perform a depth-first traversal of the graph.
- Add nodes to the result after all their descendants are visited).
  - In the example below, we add it to the beginning of the array is because we traverse in DFS manner, so when it comes the moment that we can insert the current node, all of its descendent/dependent has been added to the result
- If a back edge is detected during the traversal, the graph has a cycle.

graph = {
    0: [1, 3],
    1: [2],
    2: [3,4],
    3: [4],
    4: []
}

def explore(graph: dict, node: int, visited: list, result: list):
    visited[node] = True
    for neighbor in graph[node]:
        if visited[neighbor] is False:
            explore(graph, neighbor, visited, result)
    result.insert(0, node)

def topological_sort(graph: dict):
    visited = [False]*len(graph)
    result = list()
    
    for node in graph:
        if visited[node] is False:
            explore(graph, node, visited, result)
    
    print(result)
    
topological_sort(graph)

NOTES: There will be problem that we have to check for a cycle inside a graph, we can utilize the visited array ⇒ Rather than just storing True/False value (to signal if we have visited the node), we can store numerical value to indicate different things. For example, we can store 0 as not visited, 1 as currently visiting and traversing its neighbor, and 2 as done visiting the current node and all its neighbor. In this way we could see that if the state of the neighbor we are trying to visit is 1, that means that the graph contains a cycle.

Example: https://leetcode.com/problems/course-schedule/description/

class Solution:
    def canFinish(self, numCourses: int, pre: List[List[int]]) -> bool:
        adjList = {i: [] for i in range(numCourses)}

        for a, b in pre:
            adjList[b].append(a)
        
        visit = [0] * (numCourses + 1)
        order = []

        def dfs(course):
            visit[course] = 1
            for nb in adjList[course]:
                if visit[nb] == 1:
                    return False
                elif visit[nb] == 0 and dfs(nb) is False:
                    return False
            order.insert(0, course)
            visit[course] = 2
            return True

        for course in range(numCourses):
            if visit[course] == 0:
                if not dfs(course):
                    return False
        
        return len(order) == numCourses

https://leetcode.com/problems/course-schedule-ii

class Solution:
    def findOrder(self, numCourses: int, pre: List[List[int]]) -> List[int]:
        adjList = {i: [] for i in range(numCourses)}
        visit = [0] * (numCourses)

        for a,b in pre:
            adjList[b].append(a)

        res = []
        
        def dfs(course):
            visit[course] = 1
            for nb in adjList[course]:
                if visit[nb] == 1:
                    return False
                elif visit[nb] == 0 and dfs(nb) is False:
                    return False
            res.insert(0, course)
            visit[course] = 2
            return True
        
        for course in range(numCourses):
            if visit[course] == 0:
                # Check for cycle
                if not dfs(course):
                    return []
        
        return res

https://leetcode.com/problems/find-eventual-safe-states

 def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
    res = []
    visit = [0] * len(graph)

    def dfs(node) -> bool:
        visit[node] = 1
        for nb in graph[node]:
            if visit[nb] == 1:
                return False
            if visit[nb] == 0 and dfs(nb) is False:
                return False
        visit[node] = 2
        return True

    for i in range(len(graph)):
        if dfs(i):
            res.append(i)
    
    return res

https://leetcode.com/problems/alien-dictionary

Deduce order of character by comparing 2 adjection word
Use Topological sort to fill the order once we have the adjency graph

 def alienOrder(self, words: List[str]) -> str:
    graph = {c: [] for word in words for c in word}

    for i in range(1, len(words)):
        word1, word2 = words[i - 1], words[i]
        if len(word1) > len(word2) and word1[:len(word2)] == word2:
            return ""
        for i in range(min(len(word1), len(word2))):
            if word1[i] != word2[i]:
                graph[word1[i]].append(word2[i])
                break

    order = []
    visit = collections.defaultdict(int)

    def dfs(char):
        visit[char] = 1
        if char in graph:
            for nb in graph[char]:
                if visit[nb] == 1:
                    return False
                if visit[nb] == 0 and not dfs(nb):
                    return False
        visit[char] = 2
        order.insert(0, char)
        return True

    for char in graph.keys():
        if visit[char] == 0:
            if not dfs(char):
                return ""

    return "".join(order)

Dijkstra's Shortest Path

A [[Greedy | greedy algorithm]] used to find the shortest path from a source node to all other nodes in a weighted, non-negative graph.
General idea:
- We maintain a [[8. Heap| minHeap]] to keep track of the nodes with shortest distance from the source node
- At each step we get the node with shortest distance from the heap
- If a node is already visited we can skip it
  - Because of we make optimal choice (getting the nodes with shortest distance from the heap) every times, we can guarantee that once a node is visited, there can't be other paths that are more optimal

def djikstraShortestPath(n: int, edges: List[List[int]], src: int) -> Dict[int, int]:
    adjList = collections.defaultdict(list)

    for start, end, weight in edges:
        adjList[start].append((end, weight))

    shortestPath = {}
    minHeap = [(0, src)]

    while minHeap:
        dst, node = heapq.heappop(minHeap)
        # As we use heap, once we visit a node, we can be sure that we have the shortest path to it
        if node in shortestPath:
            continue
        shortestPath[node] = dst

        for nb, nbDist in adjList[node]:
            if nb not in shortestPath:
                heapq.heappush(minHeap, (dst + nbDist, nb))

    for i in range(n):
        if i not in shortestPath:
            shortestPath[i] = -1

    return shortestPath

Examples

https://leetcode.com/problems/minimum-path-sum

Dead simple/direct application

  def minPathSum(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    directions = [(1, 0), (0, 1)]

    minSum = [[float('inf')] * cols for _ in range(rows)]
    minSum[0][0] = grid[0][0]
    minHeap = [(grid[0][0], 0, 0)]

    while minHeap:
        curSum, row, col = heapq.heappop(minHeap)
        if curSum > minSum[row][col]:
            continue
        for rowDir, colDir in directions:
            nextRow = row + rowDir
            nextCol = col + colDir

            if nextRow not in range(rows) or nextCol not in range(cols):
                continue
            newSum = curSum + grid[nextRow][nextCol]

            if newSum < minSum[nextRow][nextCol]:
                minSum[nextRow][nextCol] = newSum
                heapq.heappush(minHeap, (newSum, nextRow, nextCol))

    return minSum[-1][-1]

https://leetcode.com/problems/minimum-genetic-mutation

Almost direct application of Djikstra

 def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
    def countMutation(start, end):
        res = 0
        for i in range(len(start)):
            if start[i] != end[i]:
                res += 1
        return res
    
    minHeap = [(0, startGene)]
    visit = set()
    visit.add(startGene)

    while minHeap:
        dist, gene = heapq.heappop(minHeap)
        if gene == endGene:
            return dist

        for validGene in bank:
            if validGene == gene:
                continue
            if countMutation(gene, validGene) > 1:
                continue
            if validGene in visit:
                continue
            heapq.heappush(minHeap, (dist + 1, validGene))
            visit.add(validGene)
    
    return -1

https://leetcode.com/problems/network-delay-time

Direct application

 def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    adjList = collections.defaultdict(list)

    for u, v, w in times:
        adjList[u].append((v, w))
    
    shortestPath = {}
    minHeap = [(0, k)]

    while minHeap:
        dst, node = heapq.heappop(minHeap)
        if node in shortestPath:
            continue
        shortestPath[node] = dst
        for nb, nbDist in adjList[node]:
            if nb not in shortestPath:
                heapq.heappush(minHeap, (dst + nbDist, nb))
    
    for i in range(1, n+1):
        if i not in shortestPath:
            return -1

    return max(shortestPath.values())

https://leetcode.com/problems/cheapest-flights-within-k-stops

  def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    adjList = collections.defaultdict(list)

    for start, end, price in flights:
        adjList[start].append((end, price))

    # Track price, stops, node respectively
    minHeap = [(0, 0, src)]
    # Modified to tracks both node and stops
    shortestPaths = {}

    while minHeap:
        price, stops, node = heapq.heappop(minHeap)
        if node == dst:
            return price
        if stops > k:
            continue
        if (node, stops) in shortestPaths and shortestPaths[(node, stops)] <= price:
            continue
        shortestPaths[(node, stops)] = price
        for nb, nbPrice in adjList[node]:
            heapq.heappush(minHeap, (price+nbPrice, stops + 1, nb))
    
    return -1

For this particular problem, it's actually easier and faster to just use BFS
- Small problem size => Heap overhead

 def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adjList = collections.defaultdict(list)

    for start, end, price in flights:
        adjList[start].append((end, price))

    queue = [(src, 0, 0)]
    cheapest = [float('inf') for i in range(n)]
    cheapest[src] = 0

    while queue:
        node, stops, price = queue.pop(0)
        if stops > k:
            continue
        
        for nb, nbPrice in adjList[node]:
            if price + nbPrice < cheapest[nb]:
                cheapest[nb] = price + nbPrice
                queue.append((nb, stops + 1, price + nbPrice))
        
    return cheapest[dst] if cheapest[dst] != float('inf') else -1

https://leetcode.com/problems/minimum-cost-to-reach-city-with-discounts/

def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
    adjList = collections.defaultdict(list)

    for start, end, cost in highways:
        adjList[start].append((end, cost))
        adjList[end].append((start, cost))
    
    minHeap = [(0, 0, discounts)]
    visit = {}

    while minHeap:
        cost, node, discountLeft = heapq.heappop(minHeap)
        if node in visit and visit[node] >= discountLeft:
            continue
        if node == n - 1:
            return cost

        visit[node] = discountLeft
        for nb, nbCost in adjList[node]:
            if discountLeft > 0:
                heapq.heappush(minHeap, (cost + nbCost // 2, nb, discountLeft - 1))
            heapq.heappush(minHeap, (cost + nbCost, nb, discountLeft))

    return -1

https://leetcode.com/problems/path-with-minimum-effort

 def minimumEffortPath(self, heights: List[List[int]]) -> int:
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    rows, cols = len(heights), len(heights[0])

    efforts = [[float('inf')] * cols for _ in range(rows)]
    efforts[0][0] = 0

    minHeap = [(0, 0, 0)]

    while minHeap:
        effort, row, col = heapq.heappop(minHeap)

        if effort > efforts[row][col]:
            continue

        for rowDir, colDir in directions:
            nextRow = row + rowDir
            nextCol = col + colDir

            if nextRow not in range(rows) or nextCol not in range(cols):
                continue
            newEffort = max(effort, abs(heights[nextRow][nextCol] - heights[row][col]))
            if newEffort < efforts[nextRow][nextCol]:
                efforts[nextRow][nextCol] = newEffort
                heapq.heappush(minHeap, (newEffort, nextRow, nextCol))

    return efforts[rows-1][cols-1]

References​

DFS​

Helpful Pattern​

BFS​

Helpful pattern​

BFS From border​

0-1 BFS​

Multisource BFS​

BFS with bit masking​

Bi-directional BFS​